/*
 * Internal interface definitions, etc., for the reg package
 *
 * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
 *
 * Development of this software was funded, in part, by Cray Research Inc.,
 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
 * Corporation, none of whom are responsible for the results.  The author
 * thanks all of them.
 *
 * Redistribution and use in source and binary forms -- with or without
 * modification -- are permitted for any purpose, provided that
 * redistributions in source form retain this entire copyright notice and
 * indicate the origin and nature of any modifications.
 *
 * I'd appreciate being given credit for this package in the documentation
 * of software which uses it, but that is not a requirement.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * src/include/regex/regguts.h
 */



/*
 * 环境定制。希望你现在阅读的文件不必进行修改——regcustom.h 应该处理所有这些，只要在这里和其他地方小心做就行。
 */
#include "regcustom.h"



/*
 * regcustom.h 可能会覆盖的内容。
 */

/* 断言 */
#ifndef assert
#ifndef REG_DEBUG
#define  NDEBUG					/* 无断言 */
#endif
#include <assert.h>
#endif

/* voids */
#ifndef DISCARD
#define DISCARD void			/* 用于丢弃值 */
#endif
#ifndef VS
#define VS(x)	((void *)(x))	/* 将某物转换为通用指针 */
#endif

/* 函数指针声明 */
#ifndef FUNCPTR
#define FUNCPTR(name, args) (*(name)) args
#endif

/* 内存分配 */
#ifndef MALLOC
#define MALLOC(n)	malloc(n)
#endif
#ifndef REALLOC
#define REALLOC(p, n)	realloc(VS(p), n)
#endif
#ifndef FREE
#define FREE(p)		free(VS(p))
#endif

/* 需要字符的位数大小，以及在有界量词中的最大值 */
#ifndef _POSIX2_RE_DUP_MAX
#define _POSIX2_RE_DUP_MAX	255 /* 通常来自 <limits.h> */
#endif



/*
 * misc
 */

#define NOTREACHED	0

#define DUPMAX	_POSIX2_RE_DUP_MAX
#define DUPINF	(DUPMAX+1)

#define REMAGIC 0xfed7			/* 主结构的魔法数字 */

/* 用于查找约束的类型代码 */
#define LATYPE_AHEAD_POS	03	/* 正向预查 */
#define LATYPE_AHEAD_NEG	02	/* 否定预测 */
#define LATYPE_BEHIND_POS	01	/* 正向前查看 */
#define LATYPE_BEHIND_NEG	00	/* 负向前查看 */
#define LATYPE_IS_POS(la)	((la) & 01)
#define LATYPE_IS_AHEAD(la) ((la) & 02)


/*
 * 调试工具
 */
#ifdef REG_DEBUG
/* FDEBUG 进行有限状态跟踪 */
#define FDEBUG(arglist) { if (v->eflags&REG_FTRACE) printf arglist; }
/* MDEBUG 进行更高级别的跟踪 */
#define MDEBUG(arglist) { if (v->eflags&REG_MTRACE) printf arglist; }
#else
#define FDEBUG(arglist) {}
#define MDEBUG(arglist) {}
#endif



/*
 * 位图操作
 */
#define UBITS	(CHAR_BIT * sizeof(unsigned))
#define BSET(uv, sn)	((uv)[(sn)/UBITS] |= (unsigned)1 << ((sn)%UBITS))
#define ISBSET(uv, sn)	((uv)[(sn)/UBITS] & ((unsigned)1 << ((sn)%UBITS)))


/*
 * 已知字符类
 */
enum char_classes
{
	CC_ALNUM, CC_ALPHA, CC_ASCII, CC_BLANK, CC_CNTRL, CC_DIGIT, CC_GRAPH,
	CC_LOWER, CC_PRINT, CC_PUNCT, CC_SPACE, CC_UPPER, CC_XDIGIT, CC_WORD
};

#define NUM_CCLASSES 14


/*
 * 尽快将字符映射到等价类——“颜色”——数量更容易管理。
 *
 * 为了进一步减少 NFA 和 DFA 中的弧数，我们还拥有一个特殊的 RAINBOW “颜色”可以分配给一条弧。这并不是真正的颜色，因为它在颜色图中没有条目。
 */
typedef short color;			/* 字符的颜色 */

#define MAX_COLOR	32767		/* 最大颜色（必须适合 'color' 数据类型） */
#define COLORLESS	(-1)		/* 不可能的颜色 */
#define RAINBOW		(-2)		/* 代表所有颜色，除了伪颜色 */
#define WHITE		0			/* 默认颜色，所有其他颜色的父颜色 */
/* 注意：代码中的多个地方知道 WHITE 是零 */


/*
 * 适用于编译时颜色机制的每种颜色数据结构
 *
 * 如果 "sub" 不是 NOSUB，则它是颜色当前子颜色的编号，即我们正在将此颜色（字符等价类）划分为两种颜色。有关子颜色的讨论，请参见 src/backend/regex/README。
 *
 * 当前未使用的颜色具有 FREECOL 位设置，并使用其“sub”字段链接到空闲链表，但仅当它们的颜色编号小于 colormap.max 时。任何超出“max”的数组项只是垃圾。
 */
struct colordesc
{
	int			nschrs;			/* 此颜色的简单字符数量 */
	int			nuchrs;			/* 此颜色的上映射条目数量 */
	color		sub;			/* 开放子颜色（如果有）；或自由链指针 */
#define  NOSUB	 COLORLESS		/* 没有开放子颜色时“sub”的值 */
	struct arc *arcs;			/* 此颜色的所有弧的链 */
	chr			firstchr;		/* 简单字符首次分配给此颜色 */
	int			flags;			/* 以下标志的位掩码: */
#define  FREECOL 01				/* 当前空闲 */
#define  PSEUDO  02				/* 伪颜色，没有真正的字符 */
#define  COLMARK 04				/* 在某些函数中使用的临时标记 */
};

#define  UNUSEDCOLOR(cd) ((cd)->flags & FREECOL)

/*
 * 颜色映射表本身
 *
 * 该结构同时包含仅在编译时使用的数据，以及 chr 到
 * 颜色映射的信息，在编译和运行时都使用。后者
 * 占据了大部分空间，因此不值得将
 * 仅用于编译的部分分离出来。
 *
 * 理想情况下，映射数据应该只是一个按 chr 代码索引的
 * 颜色数组；但对于大型字符集来说，这是不切实际的。幸运的是，
 * 常见字符的代码较小，因此我们可以对 chr
 * 代码进行简单数组处理，直到 MAX_SIMPLE_CHR，并对
 * 较大代码做更复杂的处理，而不会损失太多性能。所谓的“更复杂的”
 * 是一个颜色条目的 2-D 数组，其中行索引对应于在正则表达式中提到的
 * 单个 chr 或 chr 范围（第零行表示所有其他 chr），
 * 列索引对应于不同的基于区域的字符类集合，例如“isalpha”。 
 * 如果我们不关心此正则表达式中的第 k 个字符类，则 classbits[k]
 * 项为零；否则，当相关字符是该类的成员时，它将是要 OR 进列索引的位。
 * 我们通过识别 chr 所在的颜色映射范围来查找高值 chr 的颜色，以获得
 * 行索引（如果不在其中，则使用第零行），识别它所在的有趣字符类，以获得
 * 列索引，然后索引到 2-D hicolormap 数组中。
 *
 * colormapranges 要求非空、不重叠，并按 chr 值递增顺序出现。
 */

typedef struct colormaprange
{
	chr			cmin;			/* 范围表示 cmin..cmax 包括 */
	chr			cmax;
	int			rownum;			/* hicolormap 数组中的行索引 (>= 1) */
} colormaprange;

struct colormap
{
	int			magic;
#define  CMMAGIC 0x876
	struct vars *v;				/* 用于编译错误报告 */
	size_t		ncds;			/* colordescs 数组的分配长度 */
	size_t		max;			/* 当前使用的最高颜色号 */
	color		free;			/* 空闲链的开始（如果非 0） */
	struct colordesc *cd;		/* 指向 colordescs 数组的指针 */
#define  CDEND(cm)	 (&(cm)->cd[(cm)->max + 1])

	/* chr <= MAX_SIMPLE_CHR 的映射数据： */
	color	   *locolormap;		/* 按 chr 代码索引的简单数组 */

	/* chr > MAX_SIMPLE_CHR 的映射数据： */
	int			classbits[NUM_CCLASSES];	/* 请参见上面的注释 */
	int			numcmranges;	/* colormapranges 的数量 */
	colormaprange *cmranges;	/* 高 chr 的范围 */
	color	   *hicolormap;		/* 颜色条目的 2-D 数组 */
	int			maxarrayrows;	/* 已分配的数组行数 */
	int			hiarrayrows;	/* 正在使用的数组行数 */
	int			hiarraycols;	/* 数组列数 (2^N) */

	/* 如果我们需要多达 NINLINECDS，我们就在这里存储它们以节省 malloc */
#define  NINLINECDS  ((size_t) 10)
	struct colordesc cdspace[NINLINECDS];
};

/* 获取 chr 的颜色；注意 c 参数的多次计算 */
#define GETCOLOR(cm, c) \
	((c) <= MAX_SIMPLE_CHR ? (cm)->locolormap[(c) - CHR_MIN] : pg_reg_getcolor(cm, c))


/*
 * regc_locale.c 中区域接口函数的接口定义。
 */

/*
 * 字符集的表示。chrs[] 表示单个
 * 代码点，ranges[] 表示以 min..max 包括形式的范围。
 *
 * 如果 cvec 代表特定区域的字符类，例如 [[:alpha:]]，
 * 则 chrs[] 和 ranges[] 数组仅包含该类的成员，
 * 直到 MAX_SIMPLE_CHR（包括）。cclasscode 被设置为 regc_locale.c 的
 * 类代码，而不是普通 cvec 中的 -1。
 *
 * 注意，从 newcvec() 获取并打算通过
 * freecvec() 释放的 cvec 中，两个 chrs 数组位于结构末尾，而不是
 * 分别 malloc；因此 chrspace 和 rangespace 实质上是不可变的。
 */
struct cvec
{
	int			nchrs;			/* chr 的数量 */
	int			chrspace;		/* 在 chrs[] 中分配的 chr 数量 */
	chr		   *chrs;			/* 指向 chr 向量的指针 */
	int			nranges;		/* 范围数量（chr 对） */
	int			rangespace;		/* 在 ranges[] 中分配的范围数量 */
	chr		   *ranges;			/* 指向 chr 对的向量的指针 */
	int			cclasscode;		/* “枚举类”的值，或 -1 */
};


/*
 * NFA 内部表示的定义
 */
struct state;

struct arc
{
	int			type;			/* 如果空闲则为 0，否则为 NFA 弧类型代码 */
	color		co;				/* 弧匹配的颜色（可能是 RAINBOW） */
	struct state *from;			/* 来源 */
	struct state *to;			/* 目标 */
	struct arc *outchain;		/* 在 *from 的输出链或自由链中的链接 */
	struct arc *outchainRev;	/* *from 的外链中的反向链接 */
#define  freechain	outchain	/* 我们不维护 "freechainRev" */
	struct arc *inchain;		/* 在 *to 的输入链中的链接 */
	struct arc *inchainRev;		/* 在 *to 的输入链中的反向链接 */
	/* 当 co == RAINBOW 时，这些字段未被使用： */
	struct arc *colorchain;		/* 在颜色的弧链中的链接 */
	struct arc *colorchainRev;	/* 在颜色的弧链中的反向链接 */
};

struct arcbatch
{								/* 用于批量分配弧 */
	struct arcbatch *next;		
/* 链接 */
	size_t		narcs;			/* 在此 arcbatch 中分配的弧数 */
	struct arc	a[FLEXIBLE_ARRAY_MEMBER];
};
#define  ARCBATCHSIZE(n)  ((n) * sizeof(struct arc) + offsetof(struct arcbatch, a))
/* 第一个批次将有 FIRSTABSIZE 个弧；然后翻倍，直到 MAXABSIZE */
#define  FIRSTABSIZE	64
#define  MAXABSIZE		1024

struct state
{
	int			no;				/* 状态编号，零及以上；或 FREESTATE */
#define  FREESTATE	 (-1)
	char		flag;			/* 标记特殊状态 */
	int			nins;			/* 输入弧的数量 */
	int			nouts;			/* 输出弧的数量 */
	struct arc *ins;			/* 输入弧的链 */
	struct arc *outs;			/* 输出弧的链 */
	struct state *tmp;			/* 遍历算法的临时变量 */
	struct state *next;			/* 用于遍历所有活动状态的链 */
	/* “下一个”字段也用于将自由状态链接在一起 */
	struct state *prev;			/* 在所有活动状态链中的反向链接 */
};

struct statebatch
{								/* 用于批量分配状态 */
	struct statebatch *next;	
/* 链接 */
	size_t		nstates;		/* 此批次中分配的状态数量 */
	struct state s[FLEXIBLE_ARRAY_MEMBER];
};
#define  STATEBATCHSIZE(n)  ((n) * sizeof(struct state) + offsetof(struct statebatch, s))
/* 第一批将有 FIRSTSBSIZE 状态；然后翻倍直到 MAXSBSIZE */
#define  FIRSTSBSIZE	32
#define  MAXSBSIZE		1024

struct nfa
{
	struct state *pre;			/* 预初始化状态 */
	struct state *init;			/* 初始状态 */
	struct state *final;		/* 最终状态 */
	struct state *post;			/* 后最终状态 */
	int			nstates;		/* 用于编号状态 */
	struct state *states;		/* 活状态链 */
	struct state *slast;		/* 链的尾部 */
	struct state *freestates;	/* 空闲状态链 */
	struct arc *freearcs;		/* 空闲弧链 */
	struct statebatch *lastsb;	/* 状态批链 */
	struct arcbatch *lastab;	/* 弧批链 */
	size_t		lastsbused;		/* 从 *lastsb 中消耗的状态数 */
	size_t		lastabused;		/* 从 *lastab 中消耗的弧数 */
	struct colormap *cm;		/* 颜色映射 */
	color		bos[2];			/* 分配给 BOS 和 BOL 的颜色（如果有） */
	color		eos[2];			/* 分配给 EOS 和 EOL 的颜色（如果有） */
	int			flags;			/* 传递给 cNFA 的标志 */
	int			minmatchall;	/* 要匹配的最小字符数，如果 matchall */
	int			maxmatchall;	/* 要匹配的最大字符数，或 DUPINF */
	struct vars *v;				/* 简化编译错误报告 */
	struct nfa *parent;			/* 父 NFA（如果有） */
};



/*
 * 压缩 NFA 的定义
 *
 * 压缩 NFA 的主要节省空间来源于尽可能使弧小。我们仅存储
 * 每个弧的过渡颜色和下一个状态编号。每个状态的出弧列表是
 * 从 cnfa.states[statenumber] 开始的数组，并由一个虚拟的 carc 结构
 * 结束，其 co == COLORLESS。
 *
 * 非虚拟的 carc 结构有两种类型：普通弧和 LACON 弧。
 * 普通弧仅存储过渡颜色编号作为 "co"。LACON 弧
 * 存储环视约束编号加上 cnfa.ncolors 作为 "co"。LACON
 * 弧可以通过测试 co >= cnfa.ncolors 来区别于普通弧。
 *
 * 注意，在普通弧中，"co" 可以是 RAINBOW；因为这是负的， 
 * 它不会违反识别 LACON 弧的规则。
 *
 * 我们对可以匹配任何字符串的“琐碎” NFA 进行了特别标记
 * （可能对其中字符的数量有限制）。在这种情况下，flags & MATCHALL
 * 被设置（并且不能设置 HASLACONS）。然后字段 minmatchall 和
 * maxmatchall 给出要匹配的最小和最大字符数。例如，“.*” 
 * 产生 minmatchall = 0 和 maxmatchall = DUPINF，而 ".+" 
 * 产生 minmatchall = 1 和 maxmatchall = DUPINF。
 */
struct carc
{
	color		co;				/* COLORLESS 是列表终止符 */
	int			to;				/* 下一个状态编号 */
};

struct cnfa
{
	int			nstates;		/* 状态数量 */
	int			ncolors;		/* 颜色数量（最大使用颜色 + 1） */
	int			flags;			/* 以下标志的位掩码: */
#define  HASLACONS	01			/* 使用前瞻约束 */
#define  MATCHALL	02			/* 匹配所有长度范围内的字符串 */
#define  HASCANTMATCH 04		/* 包含CANTMATCH弧 */
	/* 注意：HASCANTMATCH出现在nfa结构的标志中，但从未出现在cnfas中 */
	int			pre;			/* 设置状态编号 */
	int			post;			/* 拆解状态编号 */
	color		bos[2];			/* 分配给 BOS 和 BOL 的颜色（如果有） */
	color		eos[2];			/* 分配给 EOS 和 EOL 的颜色（如果有） */
	char	   *stflags;		/* 每个状态标志字节的向量 */
#define  CNFA_NOPROGRESS	01	/* 无进度状态的标志位 */
	struct carc **states;		/* 指向出弧列表的指针向量 */
	/* states[n]是指向单个malloc'd弧数组的指针 */
	struct carc *arcs;			/* 列表区域 */
	/* 这些字段仅在MATCHALL NFA中使用（否则为-1）： */
	int			minmatchall;	/* 匹配的最小字符数 */
	int			maxmatchall;	/* 要匹配的最大字符数，或 DUPINF */
};

/*
 * 在调试时，如果一个未填充的CNFA全为零会很有帮助。
 * 但是在生产中，我们只要求nstates为零。
 */
#ifdef REG_DEBUG
#define ZAPCNFA(cnfa)	memset(&(cnfa), 0, sizeof(cnfa))
#else
#define ZAPCNFA(cnfa)	((cnfa).nstates = 0)
#endif
#define NULLCNFA(cnfa)	((cnfa).nstates == 0)

/*
 * 此符号限制了正则表达式编译器使用的瞬态堆空间，
 * 也限制了我们将处理的NFA的最大复杂性。
 * 目前我们只计算NFA状态和弧；其他瞬态数据通常不够大
 * 与这些相比。
 * 请注意，我们不对最终输出数据结构（
 * 压缩的NFA和颜色映射）收取任何费用。
 * 这里的缩放是基于经验测量，即大型NFA
 * 通常每个状态有大约4个弧。
 */
#ifndef REG_MAX_COMPILE_SPACE
#define REG_MAX_COMPILE_SPACE  \
	(500000 * (sizeof(struct state) + 4 * sizeof(struct arc)))
#endif

/*
 * 子表达式树
 *
 * "op" 是以下之一：
 *		'='  纯正则表达式，没有有趣的子结构（实现为DFA）
 *		'b'  回溯引用（也没有子结构）
 *		'('  无操作捕获节点：捕获其单个子节点的匹配
 *		'.'  连接：匹配第一子节点的匹配，然后是第二子节点
 *		'|'  选择：匹配任何子节点的匹配
 *		'*'  迭代：匹配其单个子节点的某些匹配
 *
 * 选择节点可以有任意数量的子节点（但至少二个），
 * 通过其兄弟字段链接。
 *
 * 连接节点必须恰好有两个子节点。 支持更多子节点可能会有用，
 * 但这会使执行者复杂化。 请注意，
 * 是第一个子节点的贪婪性决定了节点对
 * 切分匹配的位置的偏好。
 *
 * 注意：当回溯引用被直接量化时，我们将最小/最大计数
 * 放入回溯引用中，而不是在其上叠加一个迭代节点。 这是
 * 为了效率：没有必要寻找可能的分割点。
 */
struct subre
{
	char		op;				/* 见上面的类型代码 */
	char		flags;
#define  LONGER  01				/* 更倾向于更长的匹配 */
#define  SHORTER 02				/* 更倾向于更短的匹配 */
#define  MIXED	 04				/* 下面的混合偏好 */
#define  CAP	 010			/* 在这里或下面捕获的括号 */
#define  BACKR	 020			/* 在这里或下面的回溯引用 */
#define  BRUSE	 040			/* 被回溯引用引用 */
#define  INUSE	 0100			/* 在最终树中使用 */
#define  UPPROP  (MIXED|CAP|BACKR)	/* 应该向上传播的标志 */
#define  LMIX(f) ((f)<<2)		/* LONGER -> MIXED */
#define  SMIX(f) ((f)<<1)		/* 更短 -> 混合 */
#define  UP(f)	 (((f)&UPPROP) | (LMIX(f) & SMIX(f) & MIXED))
#define  MESSY(f)	 ((f)&(MIXED|CAP|BACKR))
#define  PREF(f)	 ((f)&(LONGER|SHORTER))
#define  PREF2(f1, f2)	 ((PREF(f1) != 0) ? PREF(f1) : PREF(f2))
#define  COMBINE(f1, f2) (UP((f1)|(f2)) | PREF2(f1, f2))
	char		latype;			/* LATYPE 代码，如果有环视约束 */
	int			id;				/* 子正则表达式的 ID（1..ntree-1） */
	int			capno;			/* 如果是捕获节点，捕获的子号 */
	int			backno;			/* 如果是反向引用节点，引用的子号 */
	short		min;			/* 迭代或反向引用的最小重复次数 */
	short		max;			/* 迭代或回溯引用的最大重复次数 */
	struct subre *child;		/* 第一个子节点（如果有，也即自由列表链） */
	struct subre *sibling;		/* 同一父节点的下一个子节点（如果有） */
	struct state *begin;		/* 从这里的出弧... */
	struct state *end;			/* ...以inarcs结束这里 */
	struct cnfa cnfa;			/* 压缩的NFA，如果有的话 */
	struct subre *chain;		/* 用于记账和错误清理 */
};



/*
 * 通用操作函数的函数指针表
 * 一个regex_t的re_fns指向其中之一。
 */
struct fns
{
	void		FUNCPTR(free, (regex_t *));
	int			FUNCPTR(cancel_requested, (void));
	int			FUNCPTR(stack_too_deep, (void));
};

#define CANCEL_REQUESTED(re)  \
	((*((struct fns *) (re)->re_fns)->cancel_requested) ())

#define STACK_TOO_DEEP(re)	\
	((*((struct fns *) (re)->re_fns)->stack_too_deep) ())


/*
 * regex_t内部，隐藏在一个void *
 */
struct guts
{
	int			magic;
#define  GUTSMAGIC	 0xfed9
	int			cflags;			/* 编译标志的副本 */
	long		info;			/* re_info的副本 */
	size_t		nsub;			/* re_nsub的副本 */
	struct subre *tree;
	struct cnfa search;			/* 用于快速初步搜索 */
	int			ntree;			/* 子表达式的数量，加一 */
	struct colormap cmap;
	int			FUNCPTR(compare, (const chr *, const chr *, size_t));
	struct subre *lacons;		/* 前瞻约束向量 */
	int			nlacons;		/* lacons[] 的大小；注意只有编号为 1 .. nlacons-1 的槽被使用 */
};


/* 从regcomp.c导出到regexec.c的函数原型 */
extern void pg_set_regex_collation(Oid collation);
extern color pg_reg_getcolor(struct colormap *cm, chr c);
